home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7277 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  6.4 KB
  1. Path: hubcap.clemson.edu!hubcap!mjs
  2. From: mjs@hubcap.clemson.edu (M. J. Saltzman)
  3. Newsgroups: comp.lang.c,comp.programming,sci.math
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Followup-To: comp.programming,sci.math
  6. Date: 15 Feb 96 16:07:25 GMT
  7. Organization: Clemson University
  8. Message-ID: <mjs.824400445@hubcap>
  9. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com> <4fv74c$chq@gatekeeper.alcatel.no> <4fvgbu$kmb@winx03.informatik.uni-wuerzburg.de>
  10. NNTP-Posting-Host: hubcap.clemson.edu
  11.  
  12. schoof@informatik.uni-wuerzburg.de (Jochen Schoof) writes:
  13.  
  14. >Ans now we should probably keep this away from comp.lang.c and turn to
  15. >some algorithmic group with it. Does anyone know one..?
  16.  
  17. Comp.programming would be good.  This is also appropriate for sci.math.
  18. I've directed followups to both groups.
  19.  
  20. The original problem was to write a program to determine the rightmost
  21. nonzero digit of 1000!.  Presumably this is to be done without
  22. computing too many of the remaining digits, and perhaps even without
  23. benefit of an arbitrary-precision arithmetic package (so the size of a
  24. representable integer is limited).
  25.  
  26. The full text of Schoof's post follows (comp.lang.c readers can hit 'n'):
  27.  
  28. %Sven Pran (Sven.Pran@alcatel.no) wrote:
  29. %: In article <31224679.6193@born.com>, John Cleland <clelaj@born.com> wrote:
  30. %: >
  31. %: >Don't just strip the trailing zeros, remove all digits except the last 
  32. %: >non-zero digit (which is your output) and then multiply by the next number in 
  33. %: >your sequence. This keeps the numbers down to a managable level and gives the 
  34. %: >correct answer as no more significant digit can affect the value of the LSD.
  35. %: >
  36. %:  . . . .
  37. %:
  38. %: No, it is obviously not sufficient to keep the last single non-zero digit, and 
  39. %: the problem appears to be a very interesting and intriguing one:
  40. %:
  41. %: A new trailing zero is 'created' every time the next multiplier is divisible 
  42. %: by 5, and how can we then calculate the next 'rightmost significant' digit?
  43. %:
  44. %: Example when a multiplier ends in 05:
  45. %:
  46. %: If the 'previous' factorial ended in 02 then the new factorial will end in 1 
  47. %: while if it ended in 12 then the new factorial will end in 6 (after removal of 
  48. %: trailing zeroes).
  49. %:
  50. %: Thus the SINGLE rightmost significant digit in the new factorial depends upon 
  51. %: the TWO rightmost significant digits both in the previous factorial and in the 
  52. %: multiplier.
  53. %:
  54. %: This means that we must keep track of the last TWO digits to calculate the new 
  55. %: SINGLE rightmost significant digit whenever a zero is 'created'. For similar 
  56. %: reasons we must track THREE digits to calculate the new TWO rightmost 
  57. %: significant digits - and so on.
  58. %:
  59. %: How many zeroes have been 'removed' when we reach 1000! ? The answer is 249, 
  60. %: which means that in order to maintain the precision needed we must track the 
  61. %: last 250 digits less the number of zeroes already 'removed' when N! reaches a 
  62. %: number with that many digits.
  63. %:
  64. %: This is where I get stuck. Hey - number theory specialists: How do we proceed?
  65.  
  66. % I'm far from being a specialist in number theory, but as can be seen from
  67. % my previous posting in this thread, have dealt with the problem for a while,
  68. % too. Allow me to give some explanation why the problem can be solved by
  69. % just keeping two digits stored. Assume we have two such digits m and n:
  70.  
  71. %   x = 10 * m + n;  with  0<=m<=9 and 1<=n<=9
  72.  
  73. % When multiplying to another number y the LSD of the result can be determined
  74. % by calculating LSD(n*LSD(y)) in most cases (see tabular below). 
  75.  
  76. %       n  ||  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
  77. % LSD(y)   ||     |     |     |     |     |     |     |     |     |
  78. % =========##=====#=====#=====#=====#=====#=====#=====#=====#=====#
  79. %       1  ||  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
  80. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  81. %       2  ||  2  |  4  |  6  |  8  |  *  |  2  |  4  |  6  |  8  |
  82. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  83. %       3  ||  3  |  6  |  9  |  2  |  5  |  8  |  1  |  4  |  7  |
  84. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  85. %       4  ||  4  |  8  |  2  |  6  |  *  |  4  |  8  |  2  |  6  |
  86. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  87. %       5  ||  5  |  *  |  5  |  *  |  5  |  *  |  5  |  *  |  5  |
  88. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  89. %       6  ||  6  |  2  |  8  |  4  |  *  |  6  |  2  |  8  |  2  |
  90. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  91. %       7  ||  7  |  4  |  1  |  8  |  5  |  2  |  9  |  6  |  3  |
  92. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  93. %       8  ||  8  |  6  |  4  |  2  |  *  |  8  |  6  |  4  |  2  |
  94. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  95. %       9  ||  9  |  8  |  7  |  6  |  5  |  4  |  3  |  2  |  1  |
  96. % ---------++-----+-----+-----+-----+-----+-----+-----+-----+-----+
  97.  
  98. % We only are in trouble if one of these two is 5 and the other is even
  99. % (see entries marked with *). In this case we need one more digit from 
  100. % the even number to determin the new LSD of the result which is:
  101.  
  102. %   LSD(n*LSD(y))+q*5   with q being either m if LSD(y)==5
  103. %                         or q being the next digit from y if n==5
  104.  
  105. % Storing additional digits is not neccessary. If two numbers of at least 
  106. % two digits have no zeroes in their rightmost digit, the two rightmost
  107. % digits of their product cannot both be zero and are determined from the
  108. % two rightmost digits of the two numbers. If you don't believe me feel
  109. % free to expand the tabular above for these numbers. Unfortunately you'll
  110. % have to write down 8100 entries... :-)
  111.  
  112. % Ans now we should probably keep this away from comp.lang.c and turn to
  113. % some algorithmic group with it. Does anyone know one..?
  114.  
  115. % - Jochen
  116.  
  117. % --
  118. % --------------------------------------------------------------------------
  119. %  Jochen Schoof                  mailto:schoof@informatik.uni-wuerzburg.de
  120. %  Lehrstuhl fuer Informatik II +-------------------------------------------
  121. %  Universitaet Wuerzburg       | You are just reading a .sig-light:
  122. %  D-97074 Wuerzburg (Germany)  | It is free of fat, sugar and cholesterol!
  123. % ------------------------------+-------------------------------------------
  124. %  WWW-Homepage:        http://www.informatik.uni-wuerzburg.de/staff/joscho
  125. % --------------------------------------------------------------------------
  126. -- 
  127.         Matthew Saltzman
  128.         Clemson University Math Sciences
  129.         mjs@clemson.edu
  130.